GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Jack Edmonds</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Jack Edmonds</span></h1>

</header>

</div>

<p><b>Jack R. Edmonds</b> (* <a href="5._April" title="5. April">5. April</a> <a href="1934" title="1934">1934</a>) ist ein kanadischer Informatiker und Mathematiker, der sich mit <a href="Kombinatorische_Optimierung" title="Kombinatorische Optimierung">kombinatorischer Optimierung</a> befasst.

</p>

<div class="mw-heading mw-heading2"><h2 id="Leben">Leben</h2></div>

<p>Edmonds studierte an der <a href="George_Washington_University" title="George Washington University">George Washington University</a> mit dem Bachelorabschluss 1958 und an der <a href="University_of_Maryland" class="mw-redirect" title="University of Maryland">University of Maryland</a> mit dem Masterabschluss 1959. Danach arbeitete er bis 1969 in der Abteilung <a href="Operations_Research" title="Operations Research">Operations Research</a> am <a href="National_Bureau_of_Standards" class="mw-redirect" title="National Bureau of Standards">National Bureau of Standards</a> unter Alan Goldman. 1960 wurde er an der University of Maryland mit der Schrift <i>A Combinatorial representation for oriented polyhedral surfaces</i> promoviert.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Ab 1969 war er Professor an der <a href="University_of_Waterloo" title="University of Waterloo">University of Waterloo</a>. Er lehrte dort bis zu seiner Emeritierung 1999, bis auf eine Zeit von 1991 bis 1993, in der er in einen Disput mit der Universität über einen vorgeblichen Rücktrittsbrief involviert war.

</p><p>Von ihm und <a href="Richard_M._Karp" title="Richard M. Karp">Richard M. Karp</a> stammt der <a href="Algorithmus_von_Edmonds_und_Karp" title="Algorithmus von Edmonds und Karp">Algorithmus von Edmonds und Karp</a>. 1965 veröffentlichte er den ersten polynomzeitlichen Algorithmus für das <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching</a>-Problem in der Graphentheorie (Algorithmus von Edmonds), was zeigte, dass das entsprechende Entscheidungsproblem in P ist. Das war auch die erste publizierte Diskussion der Unterscheidung zwischen polynomzeitlichen Algorithmen und solchen mit exponentieller Zeit.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Bekannt ist er auch für den Struktursatz von <a href="Tibor_Gallai" title="Tibor Gallai">Tibor Gallai</a> und Edmonds (und Edmonds-Gallai-Zerlegung), der Maximum-Matchings beschreibt, für Beiträge zur Theorie der <a href="Matroid" title="Matroid">Matroide</a> und Optimale Verzweigungen (Optimum Branchings).

</p><p>Mit <a href="Ellis_L._Johnson" title="Ellis L. Johnson">Ellis L. Johnson</a> löste er das <a href="Brieftr%C3%A4gerproblem" title="Briefträgerproblem">Briefträgerproblem</a> (<i>Chinese Postman Problem</i>) mit <a href="Matching_(Graphentheorie)" title="Matching (Graphentheorie)">Matching</a>-Methoden.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Sie zeigten, dass es in polynomialer Zeit lösbar ist (im Gegensatz zu dem scheinbar ähnlichen, aber weit schwierigeren <a href="Problem_des_Handlungsreisenden" title="Problem des Handlungsreisenden">Problem des Handlungsreisenden</a>).

</p><p>1985 erhielt er den <a href="John-von-Neumann-Theorie-Preis" title="John-von-Neumann-Theorie-Preis">John-von-Neumann-Theorie-Preis</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>David R. Lid (Herausgeber): <i>A century of excellence in standards, measurement and technology: a chronicle of selected NBS/NIST 1901-2000</i>, NIST Special Publications 958, Washington D. C. 2001</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Schriften">Schriften</h2></div>

<ul><li>Paths, trees and flowers, Canadian Journal of Mathematics, Band 17, 1965, S. 449–467</li>

<li>Matroids and the Greedy algorithm, Mathematical Programming, Band 1, 1971, S. 127–136</li>

<li>mit Richard Karp: Theoretical improvements in the algorithmic efficiency of network flow algorithms, Journal of the ACM, Band 19, 1972, S. 248–264</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://zbmath.org/authors/edmonds.jack-r">Jack R. Edmonds</a> in der Datenbank <a href="ZbMATH" title="ZbMATH">zbMATH</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.mathgenealogy.org/id.php?id=44142">Jack Edmonds</a> im <a href="Mathematics_Genealogy_Project" title="Mathematics Genealogy Project">Mathematics Genealogy Project</a> (englisch) <span style="display:none">Vorlage:MathGenealogyProject/Wartung/id verwendet</span> abgerufen am 13. März 2024.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Brian Hayes, Accidental Algorithms, American Scientist, Band 96, Januar/Februar 2008, S. 9–13</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Edmonds, Johnson <i>Matching, Euler tours and the Chinese Postman</i>, Mathematical Programming, Band 5, 1973, S. 88–124</span>

</li>

</ol>

<div>

Normdaten (Person): <a href="Library_of_Congress_Control_Number" title="Library of Congress Control Number">LCCN</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/nb2003029180">nb2003029180</a></span> | <a href="Virtual_International_Authority_File" title="Virtual International Authority File">VIAF</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://viaf.org/viaf/58590405/">58590405</a></span> | </div>

</div></div>

</div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-03-14" href="https://de.wikipedia.org/wiki/?title=Jack_Edmonds&oldid=243115414">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>